package org.usmile.algorithms.learn.tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class BinaryTree<E> {
    E e;

    BinaryTree<E> left;

    BinaryTree<E> right;

    public BinaryTree(E e) {
        this.e = e;
    }

    /**
     * 前序遍历
     */
    public List<E> preOrder() {
        List<E> result = new LinkedList<>();
        Deque<BinaryTree<E>> stack = new LinkedList<>();
        stack.push(this);
        while (!stack.isEmpty()) {
            BinaryTree<E> curr = stack.pop();
            if (curr.right != null) {
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }

            result.add(curr.e);
        }

        return result;
    }

    public List<E> preOrderRecursion() {
        List<E> result = new LinkedList<>();

        preOrderRecursion(this, result);

        return result;
    }

    private void preOrderRecursion(BinaryTree<E> node, List<E> result) {
        if (node == null) {
            return;
        }

        result.add(node.e);
        preOrderRecursion(node.left, result);
        preOrderRecursion(node.right, result);
    }


    /**
     * 中序遍历
     */
    public List<E> inOrder() {
        List<E> result = new LinkedList<>();
        Deque<BinaryTree<E>> stack = new LinkedList<>();
        BinaryTree<E> curr = this;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            BinaryTree<E> node = stack.pop();
            result.add(node.e);
            curr = node.right;
        }

        return result;
    }

    public List<E> inOrderRecursion() {
        List<E> result = new LinkedList<>();

        inOrderRecursion(this, result);

        return result;
    }

    private void inOrderRecursion(BinaryTree<E> node, List<E> result) {
        if (node == null) {
            return;
        }
        inOrderRecursion(node.left, result);
        result.add(node.e);
        inOrderRecursion(node.right, result);
    }

    /**
     * 后序遍历
     */
    public List<E> postOrder() {
        LinkedList<E> result = new LinkedList<>();
        Deque<BinaryTree<E>> stack = new LinkedList<>();
        stack.push(this);
        while (!stack.isEmpty()) {
            BinaryTree<E> curr = stack.pop();
            if (curr.left != null) {
                stack.push(curr.left);
            }
            if (curr.right != null) {
                stack.push(curr.right);
            }

            result.addFirst(curr.e);
        }

        return result;
    }

    public List<E> postOrderRecursion() {
        List<E> result = new LinkedList<>();

        postOrderRecursion(this, result);

        return result;
    }

    private void postOrderRecursion(BinaryTree<E> node, List<E> result) {
        if (node == null) {
            return;
        }
        postOrderRecursion(node.left, result);
        postOrderRecursion(node.right, result);
        result.add(node.e);
    }

    /**
     * 层序遍历
     */
    @SuppressWarnings("all")
    public List<List<E>> levelOrder() {
        List<List<E>> result = new LinkedList<>();
        Deque<BinaryTree<E>> queue = new LinkedList<>();
        queue.offer(this);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<E> level = new LinkedList<>();
            for (int i = 0; i < size; i ++) {
                BinaryTree<E> curr = queue.poll();
                level.add(curr.e);
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }

            result.add(level);
        }

        return result;
    }


    public static void main(String[] args) {
        BinaryTree<Integer> node1 = new BinaryTree<>(1);
        BinaryTree<Integer> node2 = new BinaryTree<>(2);
        BinaryTree<Integer> node3 = new BinaryTree<>(3);
        BinaryTree<Integer> node4 = new BinaryTree<>(4);
        BinaryTree<Integer> node5 = new BinaryTree<>(5);
        BinaryTree<Integer> node6 = new BinaryTree<>(6);
        BinaryTree<Integer> node7 = new BinaryTree<>(7);

        node1.left = node2;
        node1.right = node5;
        node2.left = node3;
        node2.right = node4;
        node5.left = node6;
        node5.right = node7;

        System.out.println(node1.preOrder());
        System.out.println(node1.preOrderRecursion());
        System.out.println(node1.inOrder());
        System.out.println(node1.inOrderRecursion());
        System.out.println(node1.postOrder());
        System.out.println(node1.postOrderRecursion());
        System.out.println(node1.levelOrder());
    }
}
